package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.Arrays;

public class JumpGameII {

    /**
     *  动态规划
     *  从右向左计算，
     *  如果当前柱子能直接跳到尾部，就记为1
     *  否则跳到下一个能最短到尾部的柱子，记为 min + 1
     *  最终返回 dp[0]
     *
     * @param nums 1 <= nums.length <= 1000
     *             0 <= nums[i] <= 105
     */
    public int jump1(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        for (int i = len - 2; i >= 0; i--){
            int step = nums[i];
            if (step + i >= len - 1){
                dp[i] = 1;
                continue;
            }
            int minSteps = dp[i + 1];
            for (int j = 2; j <= step; ++j){
                if (dp[j + i] < minSteps){
                    minSteps = dp[j + i];
                }
            }
            dp[i] = minSteps + 1;
        }
        return dp[0];
    }

    /**
     * 贪心算法
     * 从右向左遍历，每次遍历的下一个柱子选择能一次性跳转到当前位置的柱子中最左边的那个柱子
     *  2 3 1 1 4
     * -1 0 0 1 1
     */
    public int jump2(int[] nums) {
        int len = nums.length;
        int count = 0;
        int i = len - 1;
        while (i > 0){
            int j = 0;
            while (j < i){
                if (nums[j] + j >= i){
                    break;
                }
                j++;
            }
            i = j;
            count++;
        }
        return count;
    }

    /**
     * 正向查找
     * 将下一次跳跃能达到的最右侧记为边界，然后在边界内遍历数组，找到下一个边界，
     * 如果到达边界，增加跳跃次数并更新边界
     */
    public int jump(int[] nums) {
        int len = nums.length;
        int count = 0;
        int max = 0, right = 0;
        for (int i = 0; i < len - 1; ++i){
            max = Math.max(nums[i] + i, max);
            if (i == right){
                right = max;
                ++count;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {2, 31, 1, 1, 4};
        int jump = new JumpGameII().jump(nums);
        System.out.println(jump);
    }
}
